package com.skh.array;

/**
 *  至少是其他数字两倍的最大数
 * created by skh on 2018/8/22
 */
public class LargestNumberAtLeastTwiceOfOthers {

	/*
	在一个给定的数组nums中，总是存在一个最大元素 。

	查找数组中的最大元素是否至少是数组中每个其他数字的两倍。

	如果是，则返回最大元素的索引，否则返回-1。

	示例 1:

	输入: nums = [3, 6, 1, 0]
	输出: 1
	解释: 6是最大的整数, 对于数组中的其他整数,
	6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.


	示例 2:

	输入: nums = [1, 2, 3, 4]
	输出: -1
	解释: 4没有超过3的两倍大, 所以我们返回 -1.
	 */

	/*
	这道题让我们找一个至少是其他数字两倍的最大数字，那么我们想，首先明确的一点是这个要求的数字一定是数组中的最大数字，
	因为其是其他所有的数字的至少两倍。然后就是，如果该数字是数组中第二大的数字至少两倍的话，那么它一定是其他所有数字的至少两倍，
	所以我们可以遍历一次数组分别求出最大数字和第二大数字，然后判断一下最大数字是否是第二大数字的两倍即可，
	注意这里我们判断两倍的方法并不是直接相除，为了避免除以零的情况，我们采用减法
	 */
	public int dominantIndex(int[] nums) {
		int firstMax =0;
		int secondMax =0;
		int index = 0;
		for (int i=0;i<nums.length;i++) {
			if (nums[i] > firstMax) {
				secondMax = firstMax;
				firstMax = nums[i];
				index = i;
			} else if (nums[i] > secondMax) {
				secondMax = nums[i];
			}
		}

		return firstMax - secondMax >= secondMax ? index : -1;

	}

}
